package com.gorkr.labuladong.data_struct.bst;

import java.util.LinkedList;
import java.util.List;

/**
 * @author gorkr
 * @date 2022/05/30 08:35
 **/
public class M95UniqueBinarySearchTressii {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {

            this.val = val;
            this.left = left;
            this.right = right;

        }
    }

    public List<TreeNode> generateTrees(int n) {
        if(n==0){
            return new LinkedList<>();
        }

        return build(1,n);
    }

    // 构造区间[lo,hi]组成的BST
    List<TreeNode> build(int lo, int hi){
        LinkedList<TreeNode> res = new LinkedList<>();
        if(lo > hi){
            res.add(null);
            return res;
        }

        // 1. 穷举root节点的所有可能
        for (int i = lo; i <=hi ; i++) {
            // 2. 递归构造出左右子树的所有合法BST
            List<TreeNode> leftTree = build(lo, i - 1);
            List<TreeNode> rightTree = build(i + 1, hi);
            // 3. 给root节点穷举所有左右组合
            for (TreeNode leftTreeNode : leftTree) {
                for (TreeNode righttreeNode : rightTree) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTreeNode;
                    root.right = righttreeNode;
                    res.add(root);
                }
            }

        }
        return res;
    }






}
    